package one.chapter_3;

public class BST<Key extends Comparable<Key>, Value> implements SeqST<Key, Value> {
    private Node root;

    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;
        int N;

        public Node(Key key, Value value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }

    @Override
    public Key min() {
        return min(root).key;
    }

    private Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node);

    }

    @Override
    public Key max() {
        return null;
    }

    @Override
    public Key floor(Key key) {

        Node node = floor(root, key);
        if (node == null) {
            return null;
        }
        return node.key;
    }

    private Node floor(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            return floor(node.left, key);
        } else if (cmp == 0) {
            return node;
        }

        Node t = floor(node.right, key);
        if (t != null) {
            return t;
        } else {
            return node;
        }
    }

    @Override
    public Key ceiling(Key key) {

        Node node = ceiling(root, key);
        if (node == null) {
            return null;
        }
        return node.key;
    }

    private Node ceiling(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp == 0) {
            return node;
        } else if (cmp > 0) {
            return ceiling(node.right, key);
        }
        Node find = ceiling(node.left, key);

        if (find == null) {
            return node;
        }
        return find;
    }

    @Override
    public int rank(Key key) {
        return 0;
    }

    @Override
    public Key select(int k) {
        return null;
    }

    @Override
    public void deleteMin() {

    }

    @Override
    public void deleteMax() {

    }

    @Override
    public int size(Key lo, Key hi) {
        return 0;
    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi) {
        return null;
    }

    @Override
    public void put(Key key, Value value) {
        if (root == null)
            root = new Node(key, value, 1);
        else
            put(root, key, value);

    }

    private void put(Node node, Key key, Value value) {
        if (node != null) {
            int cmp = key.compareTo(node.key);
            if (cmp < 0) {
                if (node.left != null)
                    put(node.left, key, value);
                else
                    node.left = new Node(key, value, 1);
            } else if (cmp > 0) {
                if (node.right != null)
                    put(node.right, key, value);
                else
                    node.right = new Node(key, value, 1);
            } else {
                node.value = value;//更新
            }

            node.N = size(node.left) + size(node.right) + 1;
        }


    }

    @Override
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node node, Key key) {
        if (node == null) {
            return null;
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            return get(node.left, key);
        } else if (cmp < 0) {
            return get(node.right, key);
        } else {
            return node.value;
        }
    }

    @Override
    public void delete(Key key) {

    }

    @Override
    public Iterable<Key> keys() {
        return null;
    }

    @Override
    public boolean contains(Key key) {
        return false;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return node.N;
    }

}
